{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reverse Words in a String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reverseWords"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #反转字符串中的单词"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> ，请你反转字符串中 <strong>单词</strong> 的顺序。</p>\n",
    "\n",
    "<p><strong>单词</strong> 是由非空格字符组成的字符串。<code>s</code> 中使用至少一个空格将字符串中的 <strong>单词</strong> 分隔开。</p>\n",
    "\n",
    "<p>返回 <strong>单词</strong> 顺序颠倒且 <strong>单词</strong> 之间用单个空格连接的结果字符串。</p>\n",
    "\n",
    "<p><strong>注意：</strong>输入字符串 <code>s</code>中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"<code>the sky is blue</code>\"\n",
    "<strong>输出：</strong>\"<code>blue is sky the</code>\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \" &nbsp;hello world &nbsp;\"\n",
    "<strong>输出：</strong>\"world hello\"\n",
    "<strong>解释：</strong>反转后的字符串中不能存在前导空格和尾随空格。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"a good &nbsp; example\"\n",
    "<strong>输出：</strong>\"example good a\"\n",
    "<strong>解释：</strong>如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code> 包含英文大小写字母、数字和空格 <code>' '</code></li>\n",
    "\t<li><code>s</code> 中 <strong>至少存在一个</strong> 单词</li>\n",
    "</ul>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用&nbsp;<code>O(1)</code> 额外空间复杂度的 <strong>原地</strong> 解法。</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reverse-words-in-a-string](https://leetcode.cn/problems/reverse-words-in-a-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reverse-words-in-a-string](https://leetcode.cn/problems/reverse-words-in-a-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"the sky is blue\"', '\"  hello world  \"', '\"a good   example\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        def helper(l, r):\n",
    "            while l < r:\n",
    "                s[l], s[r] = s[r], s[l]\n",
    "                l += 1\n",
    "                r -= 1\n",
    "        helper(0, len(s)-1)\n",
    "        l = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == ' ':\n",
    "                helper(l, i-1)\n",
    "                l = i+1\n",
    "        helper(l, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        if not s:\n",
    "            return s\n",
    "        def re(s, i, j):\n",
    "\n",
    "            while i<j:\n",
    "                s[i],s[j] = s[j],s[i]\n",
    "                i+=1\n",
    "                j-=1\n",
    "        \n",
    "        re(s, 0, len(s)-1)\n",
    "        print(s)\n",
    "        pre = 0\n",
    "        for j,v in enumerate(s):\n",
    "            if v == ' ':\n",
    "                re(s, pre, j-1)\n",
    "                pre = j+1\n",
    "        print(j, pre)\n",
    "        re(s, pre, j)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        start = 0\n",
    "        end = len(s)-1\n",
    "        #翻转整个数组     \n",
    "        while start < end:\n",
    "            s[start], s[end]  =  s[end],s[start]\n",
    "            start +=1\n",
    "            end -= 1\n",
    "\n",
    "        #翻转每个单词\n",
    "        start = 0\n",
    "        end = 0\n",
    "        \n",
    "        while start < len(s):         \n",
    "            if s[start] == \" \"  or start == len(s)-1:\n",
    "                if start == len(s)-1:\n",
    "                    word_e = start\n",
    "                else:\n",
    "                    word_e = start-1\n",
    "                word_f = end \n",
    "                while word_f<word_e:\n",
    "                    s[word_f],s[word_e] = s[word_e],s[word_f]\n",
    "                    word_e -= 1\n",
    "                    word_f += 1\n",
    "                if start!= len(s)-1:\n",
    "                    end = start + 1\n",
    "            start += 1\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        def reverse(array, start, end):\n",
    "            p, q = start, end\n",
    "            while p < q:\n",
    "                array[p], array[q] = array[q], array[p]\n",
    "                p += 1\n",
    "                q -= 1\n",
    "            pass\n",
    "        reverse(s, 0, len(s) - 1)\n",
    "        p = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == ' ':\n",
    "                reverse(s, p, i - 1)\n",
    "                p = i + 1\n",
    "        reverse(s, p, len(s) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s[:] = ' '.join(''.join(s).split()[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        words = []\n",
    "        stack = []\n",
    "        for i in range(0 , len(s)):\n",
    "            if s[i] != \" \":\n",
    "                words.append(s[i])\n",
    "            if s[i] == \" \":\n",
    "                stack.append(words)\n",
    "                words = []\n",
    "            if i == len(s) - 1:\n",
    "                stack.append(words)\n",
    "        #print(stack)\n",
    "        s2 = []\n",
    "        for i in range(0, len(stack)):\n",
    "            s2.append(stack.pop())\n",
    "        #print(len(s2))\n",
    "        k = 0\n",
    "        s3 = [' '] * len(s)\n",
    "        #print(s3)\n",
    "        #print(len(s))\n",
    "        #s = [' '] * len(s)\n",
    "        for i in range(0, len(s2)):\n",
    "            #print(len(s2[i]))\n",
    "            s3[k:len(s2[i])] = s2[i]\n",
    "            #print(s)\n",
    "            if i != len(s2) - 1:\n",
    "                s3[k+len(s2[i])] = \" \"\n",
    "            k += (len(s2[i]) + 1)\n",
    "        for i in range(0, len(s)):\n",
    "            s[i] = s3[i]\n",
    "        #print(s3)\n",
    "        #s = s3\n",
    "        #print(len(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        space_index = [-1]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == \" \":\n",
    "                space_index.append(i)\n",
    "        \n",
    "        post = len(s)\n",
    "        ans = []\n",
    "        for t in reversed(space_index):\n",
    "            ans += s[t+1:post]+[' ']\n",
    "            post = t\n",
    "        for i in range(len(s)):\n",
    "            s[i] = ans[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s.reverse()\n",
    "\n",
    "        s.append(\" \")\n",
    "\n",
    "        start = 0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == \" \":\n",
    "                s[start:i]= reversed(s[start:i])\n",
    "                start = i + 1\n",
    "        print(s)\n",
    "        s.pop()# pop 最后的空格"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        i = 0\n",
    "        for j in range(len(s)):# aT bT c\n",
    "            if s[j] != \" \":\n",
    "                continue\n",
    "            self.reverse(s,i,j)\n",
    "            i = j + 1\n",
    "        self.reverse(s,i,len(s)) # aT bT cT\n",
    "        self.reverse(s,0,len(s)) # c b a\n",
    "# 定义翻转函数\n",
    "    def reverse(self,s,i,j):\n",
    "        left = i\n",
    "        right = j - 1\n",
    "        while left < right:\n",
    "            s[left],s[right] = s[right],s[left]\n",
    "            left += 1\n",
    "            right -= 1    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: [str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify str in-place instead.\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        for j in range(len(s)): # aT bT c\n",
    "            if s[j] != ' ': continue\n",
    "            self.reverse(s, i, j)\n",
    "            i = j + 1\n",
    "        self.reverse(s, i, len(s)) # aT bT cT\n",
    "        self.reverse(s, 0, len(s)) # c b a\n",
    "    def reverse(self, s, i, j):\n",
    "        for k in range(i, (i + j) // 2):\n",
    "            g = j - 1 - k + i\n",
    "            s[k], s[g] = s[g], s[k]\n",
    "\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        if not s:\n",
    "            return\n",
    "        self.reverse(s, 0, len(s)-1)\n",
    "        i = 0\n",
    "        for j in range(len(s)):\n",
    "            if s[j] == ' ':\n",
    "                self.reverse(s, i, j-1)\n",
    "                i = j + 1\n",
    "        self.reverse(s, i, j)\n",
    "    \n",
    "    def reverse(self, s, l, r):\n",
    "        while l < r:\n",
    "            s[l], s[r] = s[r], s[l]\n",
    "            l += 1\n",
    "            r -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s[:] = s[::-1]\n",
    "        l, r = -1, 0\n",
    "        while r < len(s):\n",
    "            if s[r] == \" \":\n",
    "                s[l + 1:r] = reversed(s[l + 1:r])\n",
    "                l = r\n",
    "            r += 1\n",
    "        s[l + 1:r] = reversed(s[l + 1:r])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s.reverse()\n",
    "        n = len(s)\n",
    "        t = ''\n",
    "        for i in range(n):\n",
    "            # print(t)\n",
    "            if s[i] != ' ':\n",
    "                t+=s[i]\n",
    "            elif s[i] == ' ':\n",
    "                s[i-len(t):i] = list(t[::-1])\n",
    "                t= ''\n",
    "        s[n-len(t):n] = list(t[::-1])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s.reverse()\n",
    "        n = len(s)\n",
    "        t = ''\n",
    "        for i in range(n):\n",
    "            # print(t)\n",
    "            if s[i] != ' ':\n",
    "                t+=s[i]\n",
    "            elif s[i] == ' ':\n",
    "                s[i-len(t):i] = list(t[::-1])\n",
    "                t= ''\n",
    "        s[n-len(t):n] = list(t[::-1])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        res = ' '.join(''.join(s).split(' ')[::-1])\n",
    "        for i in range(len(s)):\n",
    "            s[i] = res[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s[:]=[i for i in \" \".join(\"\".join(s).split()[::-1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        word = \"\"\n",
    "        result = \"\"\n",
    "        for c in s:\n",
    "            if c != \" \":\n",
    "                word += c\n",
    "            else:\n",
    "                result = word + \" \" + result\n",
    "                word = \"\"\n",
    "        \n",
    "        result = word + \" \" + result\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            s[i] = result[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        word = \"\"\n",
    "        result = \"\"\n",
    "        for c in s:\n",
    "            if c != \" \":\n",
    "                word += c\n",
    "            else:\n",
    "                result = word + \" \" + result\n",
    "                word = \"\"\n",
    "        \n",
    "        result = word + \" \" + result\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            s[i] = result[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s[:] = [str for str in ' '. join(''.join(s).split()[::-1])]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "\n",
    "        tmp = []\n",
    "        t = \"\"\n",
    "        for i in range(n):\n",
    "            if s[i] != \" \":\n",
    "                t += s[i]\n",
    "            else:\n",
    "                tmp.append(t)\n",
    "                t = \"\" \n",
    "        tmp.append(t)\n",
    "        \n",
    "        k = 0\n",
    "        for i in range(len(tmp)-1, -1, -1):\n",
    "            for j in range(len(tmp[i])):\n",
    "                s[k] = tmp[i][j]\n",
    "                k += 1\n",
    "            \n",
    "            if i>0:\n",
    "                s[k] = \" \"\n",
    "                k += 1\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        l = ''.join(s).split(' ')\n",
    "        l.reverse()\n",
    "        ls = ' '.join(l)\n",
    "        for i in range(len(s)):\n",
    "            s[i] = ls[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s.reverse()\n",
    "        str1= ''.join(s)\n",
    "        str_arr = str1.split(' ')\n",
    "        res = ''\n",
    "        index = 0\n",
    "        for i in str_arr:\n",
    "            length = len(i)\n",
    "            s[index:index+length]= list(i[::-1])\n",
    "            index += length + 1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        #直接模拟即可\n",
    "        a=\"\".join(s)\n",
    "        cur=a.split(\" \")[::-1]\n",
    "        res=[]\n",
    "        for i in range(len(cur)):\n",
    "            res.extend(list(cur[i]))\n",
    "            if i<len(cur)-1:\n",
    "                res.append(\" \")\n",
    "        for i in range(len(s)):\n",
    "            s[i]=res[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s[:] = list(' '.join(''.join(s).split()[::-1]))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: [str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify str in-place instead.\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        for j in range(len(s)): # aT bT c\n",
    "            if s[j] != ' ': \n",
    "                continue\n",
    "            self.reverse(s, i, j)\n",
    "            i = j + 1\n",
    "        self.reverse(s, i, len(s)) # aT bT cT\n",
    "        self.reverse(s, 0, len(s)) # c b a\n",
    "\n",
    "    def reverse(self, s, i, j):\n",
    "        for k in range(i, (i + j) // 2):\n",
    "            g = j - 1 - k + i\n",
    "            s[k], s[g] = s[g], s[k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        left, right = 0, len(s)-1\n",
    "        while left < right:\n",
    "            s[left], s[right] = s[right], s[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        last_pos = -1\n",
    "        pos = 0\n",
    "        while pos <= len(s):\n",
    "            if pos == len(s) or s[pos] == \" \":\n",
    "                left = last_pos + 1\n",
    "                right = pos - 1\n",
    "                while left < right:\n",
    "                    s[left], s[right] = s[right], s[left]\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "                last_pos = pos\n",
    "            pos += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        self.reverse(s, 0, len(s)-1)\n",
    "\n",
    "        i, j = 0, 0\n",
    "\n",
    "        while j <= len(s):\n",
    "            if j == len(s) or  s[j] == ' ' :\n",
    "                self.reverse(s, i, j-1)\n",
    "                i = j + 1\n",
    "                j = i + 1\n",
    "            else:\n",
    "                j += 1\n",
    "\n",
    "    def reverse(self, s, i, j):\n",
    "\n",
    "        k = (j - i + 1) // 2\n",
    "\n",
    "        for t in range(k):\n",
    "            s[i+t], s[j-t] = s[j-t], s[i+t]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        return \" \".join(word[::-1] for word in s.split(\" \"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: 'str') -> 'str':\n",
    "        s = s.split(' ')\n",
    "        for i in range(len(s)):\n",
    "            s[i] = s[i][::-1]\n",
    "        \n",
    "        s = ' '.join(s)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not s:\n",
    "            return ''\n",
    "        ans = ''\n",
    "        stack = []\n",
    "        for letter in s:\n",
    "            if letter != ' ':\n",
    "                stack.append(letter)\n",
    "            else:\n",
    "                stack.reverse()\n",
    "                ans += ''.join(stack) + ' '\n",
    "                stack = []\n",
    "        stack.reverse()\n",
    "        ans += ''.join(stack)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        # my ans\n",
    "        '''\n",
    "        if not s:\n",
    "            return ''\n",
    "        ans = ''\n",
    "        stack = []\n",
    "        for letter in s:\n",
    "            if letter != ' ':\n",
    "                stack.append(letter)\n",
    "            else:\n",
    "                stack.reverse()\n",
    "                ans += ''.join(stack) + ' '\n",
    "                stack = []\n",
    "        stack.reverse()\n",
    "        ans += ''.join(stack)\n",
    "        return ans\n",
    "        '''\n",
    "        # great one\n",
    "        return ' '.join([x[::-1] for x in s.split()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = '';\n",
    "        cur = s.split(' ');\n",
    "        for i in range(len(cur)):\n",
    "            x = list(cur[i]);\n",
    "            x.reverse();\n",
    "            res += ''.join(x);\n",
    "            if(i != len(cur) - 1):\n",
    "                res += ' ';\n",
    "        return res;\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        for w in s.split(' '):\n",
    "            r = w[::-1]\n",
    "            result.append(r)\n",
    "        return ' '.join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        return ' '.join([x[::-1] for x in s.split(' ')])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        tem = []\n",
    "        result = []\n",
    "        for n in s:\n",
    "            if n != \" \":\n",
    "                tem.append(n);\n",
    "            else:\n",
    "                for i in range(len(tem)):\n",
    "                    result.append(tem[-i-1]);\n",
    "                result.append(\" \");\n",
    "                tem = [];\n",
    "        for i in range(len(tem)):\n",
    "            result.append(tem[-i-1]);\n",
    "        return \"\".join(result);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        length=len(s)\n",
    "        print(length)\n",
    "        list1=list(s)\n",
    "        i=j=0\n",
    "        string2=\"\"\n",
    "        while i<length:\n",
    "            if list1[i]!=\" \":\n",
    "                i+=1\n",
    "            else:\n",
    "                string2+=(\"\".join(list1[j:i][::-1])+\" \")\n",
    "                j=i+1\n",
    "                i+=1\n",
    "        #string2.strip()\n",
    "        if j<length:\n",
    "            string2+=\"\".join(list1[j:length][::-1])\n",
    "        print(len(string2))\n",
    "        return string2\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        a=[]\n",
    "        for i in s:\n",
    "            a.append(i)\n",
    "        a.reverse()\n",
    "        b=''.join(a)\n",
    "        c=[]\n",
    "        d=b.split(' ')\n",
    "        for i in d:\n",
    "            c.append(i)\n",
    "        c.reverse()\n",
    "        e=' '.join(c)\n",
    "        return e\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if s==\"\":return \"\"\n",
    "        lis=s.split(' ')\n",
    "        key=lis[0]\n",
    "        print(type(key))\n",
    "        print(key[-1])\n",
    "        print(key)\n",
    "        for i,key in enumerate(lis):\n",
    "            lis[i]=key[::-1]\n",
    "        ans=' '.join(lis)\n",
    "        print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return \" \".join([i[::-1] for i in s.split()])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return \" \".join(s[::-1] for s in s.split(\" \"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return ' '.join(i[::-1] for i in s.split(' '))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        sList = list(s)\n",
    "        sList.append(' ')\n",
    "        bigList = []\n",
    "        alist = []\n",
    "        for i in sList:\n",
    "            if i != ' ':\n",
    "                alist.append(i)\n",
    "            else:\n",
    "                bigList.append(alist)\n",
    "                alist = []\n",
    "        s_list = []\n",
    "        for m in range(len(bigList)):\n",
    "            n = len(bigList[m])\n",
    "            for j in range(n):\n",
    "                s_list.append(bigList[m][n-j-1])\n",
    "                if j == n-1 and m != len(bigList) -1:\n",
    "                    s_list.append(' ')\n",
    "\n",
    "        return  \"\".join(s_list)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not s:\n",
    "            return \"\"\n",
    "        s = [i for i in s]\n",
    "        s = s[::-1]\n",
    "        tt = []\n",
    "        for i in range(len(s)):\n",
    "            if i == 0 and s[i] != \" \" and s[i+1] != \" \":\n",
    "                tt.append(i)\n",
    "            elif i > 0 and i+1 < len(s) and s[i] != \" \" and ((s[i-1] == \" \" and s[i+1] != \" \") or (s[i-1] != \" \" and s[i+1] == \" \")):\n",
    "                tt.append(i)\n",
    "            elif i == len(s)-1 and s[i] != \" \" and s[i-1] != \" \":\n",
    "                tt.append(i)\n",
    "        for i in range(0, len(tt)-1, 2):\n",
    "            end = (tt[i] + tt[i+1]) // 2 + 1\n",
    "            for j in range(tt[i], end):\n",
    "                s[j], s[tt[i] + tt[i+1] - j] = s[tt[i] + tt[i+1] - j], s[j]\n",
    "        s = s[::-1]\n",
    "        res = \"\"\n",
    "        for i in s:\n",
    "            res += i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        ans = ''\n",
    "        k = 0\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == ' ':\n",
    "                ans += s[k:i][::-1] + ' '\n",
    "                k = i+1\n",
    "                i += 1\n",
    "            i += 1\n",
    "        return ans + s[k:][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        tmp = s.split()\n",
    "        for i in range(len(tmp)):\n",
    "            tmp[i] = tmp[i][::-1]\n",
    "        return ' '.join(tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        s = s + \" \"\n",
    "        stack, res = [], \"\"\n",
    "        for i in s:\n",
    "            stack.append(i)\n",
    "            if i == \" \":\n",
    "                while(stack):\n",
    "                    res = res + stack.pop()\n",
    "        return res[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        words = s.split()\n",
    "        newwords = \"\"\n",
    "        for word in words:\n",
    "            newwords += word[::-1] + \" \"\n",
    "        return newwords[:-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        if not s:\n",
    "            return s\n",
    "        s_reverse,left=\"\",0\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==\" \":\n",
    "                s_reverse += s[left:i][::-1]+\" \"\n",
    "                left = i+1\n",
    "        s_reverse += s[left:][::-1] \n",
    "        return s_reverse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        ls = s.split(' ')\n",
    "        for i in range(len(ls)):\n",
    "            ls[i] = ls[i][::-1]\n",
    "        return ' '.join(ls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        itr = map(reversed,s.split())\n",
    "        ans = []\n",
    "        for i in itr:\n",
    "            temp = ''.join(list(i))\n",
    "            ans.append(temp)\n",
    "        return ' '.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        ans = \"\"\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            j = i\n",
    "            while j < len(s) and s[j] != \" \":\n",
    "                j += 1\n",
    "            j -= 1\n",
    "            temp = s[i:j+1]\n",
    "            ans += temp[::-1]\n",
    "            ans += \" \"\n",
    "            i = j + 2\n",
    "        return ans[:-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        return ' '.join([i[::-1] for i in s.split(' ') ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        space = list()\n",
    "        start = 0\n",
    "        for index, item in enumerate(s):\n",
    "            if item == \" \":\n",
    "                space.append(list(reversed(list(s[start:index]))))\n",
    "                space.append(\" \")\n",
    "                start = index + 1\n",
    "            elif index == len(s)-1:\n",
    "                space.append(list(reversed(list(s[start:index+1]))))\n",
    "            \n",
    "        return \"\".join([\"\".join(item) for item in space])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        if s==\"\":\n",
    "            return s\n",
    "        s_list=[a for a in s]\n",
    "\n",
    "        st,ed=0,0\n",
    "        for ed in range(0,len(s_list)):\n",
    "            if s_list[ed]!=\" \":\n",
    "                continue\n",
    "\n",
    "            self.reverse(s_list,st,ed-1)\n",
    "            st=ed+1\n",
    "        \n",
    "        self.reverse(s_list,st,ed)\n",
    "\n",
    "        ret=\"\"\n",
    "        for a in s_list:\n",
    "            ret+=a\n",
    "        return ret\n",
    "\n",
    "    def reverse(self,s_list,st,ed):\n",
    "        # print(st,ed)\n",
    "        for i in range((ed-st)//2+1):\n",
    "            s_list[st+i],s_list[ed-i]=s_list[ed-i],s_list[st+i]\n",
    "        # print(s_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        return \" \".join(s[::-1].split(\" \")[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        return ' '.join(s.split(\" \")[::-1])[::-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        return ' '.join(s.split()[::-1])[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        return \" \".join(word[::-1] for word in s.split(\" \"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        tmp = []\n",
    "        for each in s.split():\n",
    "            tmp.append(each[::-1])\n",
    "        res = ' '.join(tmp)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        s_array = list(s)\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            start = i\n",
    "            while i < n and s_array[i] != \" \":\n",
    "                i += 1\n",
    "            left, right = start, i-1\n",
    "            while left < right:\n",
    "                s_array[left], s_array[right] = s_array[right], s_array[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            while i < n and s_array[i] == \" \":\n",
    "                i += 1\n",
    "        return \"\".join(s_array)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        # 将字符串按空格分割成单词列表\n",
    "        words = s.split()\n",
    "\n",
    "        # 遍历单词列表，反转每个单词\n",
    "        for i in range(len(words)):\n",
    "            words[i] = words[i][::-1]\n",
    "\n",
    "        # 将反转后的单词列表用空格连接成新的字符串\n",
    "        result = ' '.join(words)\n",
    "\n",
    "        return result\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        s = s.split()\n",
    "        for i in range(len(s)):\n",
    "            temp = [_ for _ in s[i]]\n",
    "            l = 0\n",
    "            r = len(temp) - 1\n",
    "            while l < r:\n",
    "                temp[l], temp[r] = temp[r], temp[l]\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            s[i] = ''.join(temp)\n",
    "        return ' '.join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        # 方法1\n",
    "        # s_list = s.split(' ')\n",
    "        # for i in range(len(s_list)):\n",
    "        #     s_list[i] = s_list[i][::-1]\n",
    "        # return ' '.join(s_list)\n",
    "        # return ' '.join(word[::-1] for word in s.split(' '))\n",
    "        return ' '.join([word[::-1] for word in s.split(' ')])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        list2=[i[::-1] for i in s.split()]\n",
    "        return ' '.join(list2)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        words = s.split()[::-1]\n",
    "        ans = ''\n",
    "        for i in words:\n",
    "            if i != ' ':\n",
    "                ans += i + ' '\n",
    "        return ans[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        return ' '.join(s.split()[::-1]).strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        s = s.strip() #\n",
    "        res = \"\"\n",
    "        i, j = len(s) - 1, len(s)\n",
    "        while i > 0:\n",
    "            if s[i] == ' ':\n",
    "                res += s[i + 1: j] + ' '\n",
    "                while s[i] == ' ': i -= 1\n",
    "                j = i + 1\n",
    "            i -= 1\n",
    "        return res + s[:j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        return \" \".join(s.strip().split()[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        s = s.strip()\n",
    "        i, j = len(s)-1, len(s)\n",
    "        res = ''\n",
    "        while i > 0:\n",
    "            if s[i] == ' ':\n",
    "                res += s[i+1:j] + ' '\n",
    "                while s[i] == ' ':\n",
    "                    i -= 1\n",
    "                j = i + 1\n",
    "            else:\n",
    "                i -= 1\n",
    "        return res + s[:j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        s = s.strip().split()\n",
    "        return (' '.join(s[::-1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        return \" \".join(s.split()[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        words = s.strip().split()\n",
    "        words.reverse()\n",
    "        \n",
    "        print(words)\n",
    "        return ' '.join(words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        s = s.split()\n",
    "        s.reverse()\n",
    "        return \" \".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        s_list = self.s_split(s)\n",
    "        # print(s_list)\n",
    "        self.s_reverse(s_list)\n",
    "        return ' '.join(s_list)\n",
    "\n",
    "    def s_split(self, s):\n",
    "        n = len(s)\n",
    "\n",
    "        # 去除字符串首的空白字符和字符串尾的空白字符\n",
    "        l, r = 0, n - 1\n",
    "        while l < n and s[l] == \" \": l += 1\n",
    "        while r > 0 and s[r] == \" \": r -= 1\n",
    "        if l > r: return []\n",
    "        s = s[l: r + 1]\n",
    "        if len(s) == 1: return [s]\n",
    "        print(s)\n",
    "        \n",
    "        # 去除字符串间的空白字符\n",
    "        output = []\n",
    "        l, r = 0, 1\n",
    "        while r <= len(s):\n",
    "            while r < len(s) and s[r] != \" \": r += 1\n",
    "            output.append(s[l:r])\n",
    "\n",
    "            while r < len(s) and s[r] == \" \": r += 1\n",
    "            l, r = r, r + 1\n",
    "            print(output, l, r, len(s))\n",
    "        # print(s[27])\n",
    "        return output\n",
    "\n",
    "    def s_reverse(self, s_list):\n",
    "        n = len(s_list)\n",
    "        l, r = 0, n - 1\n",
    "        while l < r:\n",
    "            s_list[l], s_list[r] = s_list[r], s_list[l]\n",
    "            l += 1\n",
    "            r -= 1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trim_spaces(self, s: str) -> list:\n",
    "        left, right = 0, len(s) - 1\n",
    "        # 去掉字符串开头的空白字符\n",
    "        while left <= right and s[left] == ' ':\n",
    "            left += 1\n",
    "        \n",
    "        # 去掉字符串末尾的空白字符\n",
    "        while left <= right and s[right] == ' ':\n",
    "            right -= 1\n",
    "        \n",
    "        # 将字符串间多余的空白字符去除\n",
    "        output = []\n",
    "        while left <= right:\n",
    "            if s[left] != ' ':\n",
    "                output.append(s[left])\n",
    "            elif output[-1] != ' ':\n",
    "                output.append(s[left])\n",
    "            left += 1\n",
    "        \n",
    "        return output\n",
    "            \n",
    "    def reverse(self, l: list, left: int, right: int) -> None:\n",
    "        while left < right:\n",
    "            l[left], l[right] = l[right], l[left]\n",
    "            left, right = left + 1, right - 1\n",
    "            \n",
    "    def reverse_each_word(self, l: list) -> None:\n",
    "        n = len(l)\n",
    "        start = end = 0\n",
    "        \n",
    "        while start < n:\n",
    "            # 循环至单词的末尾\n",
    "            while end < n and l[end] != ' ':\n",
    "                end += 1\n",
    "            # 翻转单词\n",
    "            self.reverse(l, start, end - 1)\n",
    "            # 更新start，去找下一个单词\n",
    "            start = end + 1\n",
    "            end += 1\n",
    "                \n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        l = self.trim_spaces(s)\n",
    "        \n",
    "        # 翻转字符串\n",
    "        self.reverse(l, 0, len(l) - 1)\n",
    "        \n",
    "        # 翻转每个单词\n",
    "        self.reverse_each_word(l)\n",
    "        \n",
    "        return ''.join(l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeExtraSpace(self, s, start, end):\n",
    "        if start > end:\n",
    "            return []\n",
    "\n",
    "        slow = 0\n",
    "        fast = 0\n",
    "        length = len(s)\n",
    "        word_count =  0\n",
    "\n",
    "        while length > 0 and s[length - 1] == ' ':\n",
    "            length -= 1\n",
    "\n",
    "        while True:\n",
    "            while fast < length and s[fast] == ' ':\n",
    "                fast += 1\n",
    "\n",
    "            if word_count > 0:\n",
    "                s[slow] = ' '\n",
    "                slow += 1\n",
    "            \n",
    "            while fast < length and s[fast] != ' ':\n",
    "                s[slow] = s[fast]\n",
    "                slow += 1\n",
    "                fast += 1\n",
    "\n",
    "            word_count += 1\n",
    "\n",
    "            if fast >= length:\n",
    "                break \n",
    "\n",
    "        return s[:slow] \n",
    "    \n",
    "    def helper(self, char_array, start, end):\n",
    "        while start < end:\n",
    "            char_array[start], char_array[end] = char_array[end], char_array[start]\n",
    "            start += 1\n",
    "            end -= 1\n",
    "    \n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        if s == None or len(s) == 0:\n",
    "            return \"\"\n",
    "        \n",
    "        # 1. 去除多余空格\n",
    "        char_array = list(s)\n",
    "        char_array = self.removeExtraSpace(char_array, 0, len(char_array) - 1)\n",
    "\n",
    "        # 2. 反转每个单词\n",
    "        slow = 0\n",
    "        fast = 0\n",
    "        length = len(char_array)\n",
    "\n",
    "        while True:\n",
    "            slow = fast\n",
    "            while fast < length and char_array[fast] != ' ':\n",
    "                fast += 1\n",
    "\n",
    "            self.helper(char_array, slow, fast - 1)\n",
    "\n",
    "            fast += 1\n",
    "\n",
    "            if fast >= length:\n",
    "                break\n",
    "\n",
    "        # 3. 反转整个字符串\n",
    "        self.helper(char_array, 0, length - 1)\n",
    "\n",
    "        return ''.join(char_array)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        s = s.strip() # 删除字符串首尾空格，函数默认删除首尾的空格\n",
    "        i = j = len(s) - 1\n",
    "        res = []\n",
    "        while i >= 0:\n",
    "            while i >= 0 and s[i] != ' ': i -= 1 # 防止索引越界\n",
    "            res.append(s[i + 1 : j + 1])\n",
    "            while s[i] == ' ': i -= 1\n",
    "            j = i\n",
    "        return ' '.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        return ' '.join(s.split()[::-1])\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        return \" \".join(reversed(s.split()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        s=s.split()[::-1]\n",
    "        ans=''\n",
    "        for i in s:\n",
    "            if i==' ':\n",
    "                continue\n",
    "            else:\n",
    "                ans+=i\n",
    "                ans+=' '\n",
    "        return ans[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "#  1\n",
    "# class Solution:\n",
    "#     def reverseWords(self, s: str) -> str:\n",
    "#         return \" \".join(reversed(s.split()))\n",
    "\n",
    "\n",
    "\n",
    "# 2 太烦了,不好,!!!!对于字符串不可变的语言，首先得把字符串转化成其他可变的数据结构，同时还需要在转化的过程中去除空格。\n",
    "\n",
    "# 3 双端队列\n",
    "\n",
    "# 4 类似345\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        words=s.split(' ')\n",
    "        new=[]\n",
    "        for i  in words:\n",
    "            if i!='':\n",
    "                new.append(i)\n",
    "        n=len(new)\n",
    "        # 不知道循环多少次,用while 不用for\n",
    "        i=0\n",
    "        j=n-1 \n",
    "        while i<j and i<n and j>-1:\n",
    "            new[i],new[j]=new[j],new[i]\n",
    "            i+=1\n",
    "            j-=1\n",
    "            print(i,j)\n",
    "        return ' '.join(new)\n",
    "       \n",
    "\n",
    "                  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        i = 0\n",
    "        tmp = ''\n",
    "        res = []\n",
    "        while i<len(s):\n",
    "            if s[i] != ' ':\n",
    "                tmp+=s[i]\n",
    "            elif tmp:\n",
    "                res.append(tmp)\n",
    "                tmp = ''\n",
    "            i+=1\n",
    "        if tmp:\n",
    "            res.append(tmp)\n",
    "        return ' '.join(res[::-1])\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        res = []\n",
    "        n = len(s)\n",
    "        left, right = n - 1, n - 1       \n",
    "        while left >= 0:\n",
    "            while left >= 0 and s[left] == ' ':\n",
    "                left -= 1\n",
    "            if left == -1: break\n",
    "            right = left          \n",
    "            while left >= 0 and s[left] != ' ':\n",
    "                left -= 1\n",
    "            # print(left, right, s[left + 1: right + 1])\n",
    "            res.append(s[left + 1: right + 1])\n",
    "        # print(len(res))\n",
    "        return \" \".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        new_str = s.split()\n",
    "        new_str.reverse()\n",
    "        return ' '.join(new_str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        return \" \".join(reversed(s.split()))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
